/*!
 * \file heurPartiteSubgraph.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Heuristics for coloring, maximum stable set and maximum clique.
 */

#include <stdlib.h>
#include <bitmap.h>
#include <graph.h>
#include <heurPartiteSubgraph.h>

static BitMap * RR; 		//!< Auxiliary bitmap used in various heuristics.
static Graph * heurg; 		//!< Input graph of the heuristics.
static size_t memsz = 0;	//!< Memory space used by the heuristics.

// mcsColoring
static int * nextInColor = NULL; //!< Vertices classified by colors

// fracColoring
//static NODETYPE * E = NULL; //!< Auxiliary bitmap used in \c fracColoring.
//static NODETYPE * EE; //!< Auxiliary bitmap used in \c fracColoring.
//static NODETYPE * S; //!< Auxiliary bitmap used in \c fracColoring.

void initHeur(Graph * g) {
	heurg = g;

	RR = (BitMap *) newBitMap(g->n);

//	memsz += (nnodes << LOGW);
	nextInColor = NULL;
}

void closeHeur() {
	freeBitMap(RR);
//	free(RR);

	RR = NULL;
	heurg = NULL;

	if (nextInColor != NULL) {
		free(nextInColor);
		nextInColor = NULL;
	}

//	if (E != NULL) {
//		free(E);
//		E = NULL;
//		EE = NULL;
//	}
}

size_t getMemSize() {
	return memsz;
}

/*!
 * \fn int maxClique(BitMap * R)
 * \brief Greedy heuristic for maximum clique.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum clique.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 *
 * \return The size of the clique found.
 */
int maxClique(BitMap * R) {
	int size = 0;
	Node nodeRR;

	copyAll(RR, R);
	for (begin(RR, &nodeRR); !end(&nodeRR); next(&nodeRR)) {
		retainFrom(RR, neig(heurg, getElement(&nodeRR)), &nodeRR);
//		delElement(RR, &nodeidx);

		size++;
	}

	return size;
}

/*!
 * \fn int greedyColoring(BitMap * R, BitMap * W, int lim)
 * \brief Greedy heuristic for vertex coloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 *
 * \return The number of colors used.
 */
int greedyColoring(BitMap * R, BitMap * W, int lim) {
	int size = 0;
	Node nodeR;
	Node nodeRR;

	begin(R, &nodeR);
	beginWhile(RR, &nodeRR);
	while (size < lim && !end(&nodeR)) {
		copySets(&nodeRR, &nodeR);
		do {
			removeFrom(&nodeRR, neig(heurg, getElement(&nodeRR)));
//			delElement(RR, &nodeRR);
			delElement(R, &nodeRR);
			addElement(W, &nodeRR);
			next(&nodeRR);
		} while (!end(&nodeRR));

		size++;
		next(&nodeR);
	}

	return size;
}

/*!
 * \fn void maxStab(BitMap * R, BitMap * W, int u)
 * \brief Greedy heuristic for maximum stable set containing a specified vertex.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum stable set. The vertices in the stable set found are removed from
 * the input bitmap and stored in the output bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param u The vertex to expand to a stable set.
 */
void maxStab(BitMap * R, BitMap * W, int u) {
	Node nodeRR;

	copyAll(RR, R);
	removeAll(RR, neig(heurg, u));

	for (begin(RR, &nodeRR); !end(&nodeRR); next(&nodeRR)) {
		removeFrom(&nodeRR, neig(heurg, getElement(&nodeRR)));
//		delElement(RR, &nodeRR);
		delElement(R, &nodeRR);
		addElement(W, &nodeRR);
	}
}

/*!
 * \fn int expClique(BitMap * R, int * C, int topC)
 * \brief Greedy heuristic for expanding a specified clique.
 *
 * The vertices in the specified bitmap are greedily searched to entering the specified clique.
 *
 * \param R Input bitmap of vertices to color.
 * \param C The input clique.
 * \param topC Size of input clique.
 *
 * \return The size of the expanded clique.
 */
int expClique(BitMap * R, int * C, int size) {
	Node nodeRR;

	copyAll(RR, R);

	int t = size;
	while (--t >= 0)
		retainAll(RR, neig(heurg, C[t]));

	for (begin(RR, &nodeRR); !end(&nodeRR); next(&nodeRR)) {
		retainFrom(RR, neig(heurg, getElement(&nodeRR)), &nodeRR);
//		delElement(RR, &nodeidx);

		size++;
	}

	return size;
}

//int maxCliqueWith(NODETYPE * R, NODETYPE * W, int u, int minRNode, int maxRNode,
//		int minWNode, int maxWNode) {
//	int nodeidx = maxRNode;
//	int minRRNode = minRNode;
//	copyAll(RR, R, minRNode, nodeidx + 1);
//	addAll(RR, W, minWNode, maxWNode + 1);
//	if (maxWNode > nodeidx)
//		nodeidx = maxWNode;
//	if (minWNode < minRRNode)
//		minRRNode = minWNode;
//
//	int size = 0;
//
//	retainAll(RR, NEIG(heurg, u), minRRNode, nodeidx + 1);
//	nodeidx = maxNode(RR, nodeidx, minRRNode);
//	size++;
//
//	NODETYPE * nodeRR = (RR + nodeidx);
//	int vidx = NODEMOST(*nodeRR);
//	while (nodeidx > minRRNode && vidx >= 0) {
//		size++;
//		retainAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), minRRNode, nodeidx + 1);
//		*nodeRR = DELFROMNODE(*nodeRR, vidx);
//		nodeidx = maxNode(RR, nodeidx, minRRNode);
//		nodeRR = (RR + nodeidx);
//		vidx = NODEMOST(*nodeRR);
//	}
//	if (nodeidx == minRNode)
//		while (*nodeRR != 0 && vidx >= 0) {
//			size++;
//			retainAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), minRRNode,
//					nodeidx + 1);
//			*nodeRR = DELFROMNODE(*nodeRR, vidx);
//			vidx = NODEMOST(*nodeRR);
//		}
//
//	return size;
//}

static void printStackColor(int size) {
	int p, a;
	printf("%d-coloring:\n", size);
	for (p = 0; p < size; p++) {
		printf("color %d:", p);
		a = nextInColor[heurg->n + p];
		while (a < heurg->n) {
			printf(" %d", a);
			a = nextInColor[a];
		}
		printf("\n");
	}
}

static int checkStackColor(BitMap * R, BitMap * W, int size, char * str) {
	int p, a, b, q = 0;
	for (p = 0; p < size; p++) {
		a = nextInColor[heurg->n + p];
		if (hasElement(R, a) || !hasElement(W, a)) {
			printf("%s  color=%d  size=%d  a=%d  ISINR=%d  ISINW=%d\n", str, p, size, a, hasElement(R, a), hasElement(W, a));
			q = 1;
		}
		while (a < heurg->n) {
			b = nextInColor[a];
			while (b < heurg->n) {
				if (hasElement(neig(heurg, a), b)) {
					printf("%s  color=%d  a=%d  b=%d\n", str, p, a, b);
					q = 1;
				}
				b = nextInColor[b];
			}
			a = nextInColor[a];
		}
	}

	return q;
}

/*!
 * \fn void mcsRecolor(BitMap * R, BitMap * W, int size)
 * \brief Greedy heuristic for recoloring vertices by color exchanges.
 *
 * For every vertex \c p in the input bitmap, attempt to find a vertex \c q in the \c cover array such that the number of neighbors \c r
 * of \c p in the color \c k1 of \c q is at most 1. If such \c q is found, there are two cases. If \c r \c = \c 0, then add \c p to color
 * \c k1, updating \c cover and \c idx arrays. If \c r \c = \c 1, then attempt to find a color \c k2 containing no neighbors
 * in color \c k2. If such color \c k2 is found, then move \c q to color \c k2 and add \c p to color \c k1, removing it from the
 * input bitmap.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param size Number of colors.
 *
 * \return The number of colors used.
 */
static void mcsRecolor(BitMap * R, BitMap * W, int size) {
	int sentinel = heurg->n << 1;

	Node node;
	int u = 0, v = 0, prevu, hasv;
	copyAll(RR, R);
	for (begin(RR, &node); (hasv = !end(&node)); next(&node)) {
		v = getElement(&node);
		int ucolor = 0;
		while (ucolor < size - 1) {
			int curInColor = nextInColor[heurg->n + ucolor];
			int prevInColor = heurg->n + ucolor;
			int hasNeig = 0;
			while (hasNeig < 2 && curInColor < heurg->n) {
				if (hasEdge(heurg, v, curInColor)) {
					hasNeig++;
					u = curInColor;
					prevu = prevInColor;
				}
				prevInColor = curInColor;
				curInColor = nextInColor[curInColor];
			}

			if (hasNeig < 2) {
				int w, wcolor = -1;
				if (hasNeig == 0) {
					w = v;
					wcolor = ucolor;
				} else {
					int cl = ucolor + 1;
					while (cl < size) {
						int cc = nextInColor[heurg->n + cl];
						while (cc < sentinel && !hasEdge(heurg,u,cc))
							cc = nextInColor[cc];
						if (cc == sentinel) {
							w = u;
							wcolor = cl;
							nextInColor[prevu] = nextInColor[u];
							nextInColor[v] = nextInColor[heurg->n + ucolor];
							nextInColor[heurg->n + ucolor] = v;
							cl = size;
						} else
							cl++;
					}
				}

				if (wcolor >= 0) {
					nextInColor[w] = nextInColor[heurg->n + wcolor];
					nextInColor[heurg->n + wcolor] = w;
//					delElement(RR, &node);
					delElement(R, &node);
					addElement(W, &node);
					ucolor = size;
					hasv = 0;

//					if (checkStackColor(R, W, size, "mcsRecolor v")) {
//						printf("v=%d  u=%d  w=%d\n",v,u,w);
//						printStackColor(size);
//						exit(0);
//					}
				}
			}
			ucolor++;
		}

		if (hasv)
			retainAll(RR, neig(heurg, v));
	}

//	checkStackColor(R, W, size, "mcsRecolor");
}

/*!
 * \fn int stackColoring(BitMap * R, BitMap * W, int lim)
 * \brief Greedy heuristic for vertex coloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 * The colors created are represented in \c cover and \c idx arrays.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 *
 * \return The number of colors used.
 */
static int stackColoring(BitMap * R, BitMap * W, int lim) {
	int sentinel = heurg->n << 1;

	if (nextInColor == NULL) {
		nextInColor = (int *) calloc((heurg->n + 1) << 1, sizeof(int));
		memsz += (((heurg->n + 1) * sizeof(int)) << 1);
	}

	nextInColor[heurg->n] = sentinel;

	int size = 0;
	Node nodeR;
	Node nodeRR;

	begin(R, &nodeR);
	beginWhile(RR, &nodeRR);
	while (size < lim && !end(&nodeR)) {
		copySets(&nodeRR, &nodeR);
//		printf("greedy-cor %d:",size);
//		printSetNodes(RR);
		do {
			int v = getElement(&nodeRR);
//			printf(" %d",v);
			removeFrom(&nodeRR, neig(heurg, v));
//			delElement(RR, &nodeRR);
			delElement(R, &nodeRR);
			addElement(W, &nodeRR);

			nextInColor[v] = nextInColor[heurg->n + size];
			nextInColor[heurg->n + size] = v;
			next(&nodeRR);
		} while (!end(&nodeRR));

		nextInColor[heurg->n + (++size)] = sentinel;
		next(&nodeR);

//		printf("\n");
	}

	return size;
}

/*!
 * \fn int mcsColoring(BitMap * R, BitMap * W, int lim)
 * \brief Greedy heuristic for vertex coloring, with vertex recoloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 *
 * \return The number of colors used.
 */
int mcsColoring(BitMap * R, BitMap * W, int lim) {
	if (lim <= 2 || lim < heurg->maxcq - (heurg->maxcq >> 2))
		return greedyColoring(R, W, lim);

	int size = stackColoring(R, W, lim);
//	printStackColor(size);
	if (lim == size && isNotEmpty(R))
		mcsRecolor(R, W, size);

	return size;
}

void mcsColoring_f(BitMap * R, BitMap * W, int lim) {
	if (lim <= 1)
		greedyColoring(R, W, lim);
	else {
		int size = stackColoring(R, W, lim);
		if (isNotEmpty(R))
			mcsRecolor(R, W, size);
	}
}

/*!
 * \fn int fracColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for fractional coloring.
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greatest index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greatest index of a non-zero node of the output bitmap.
 *
 * \return The number of colors used.
 */
//int fracColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode,
//		int * maxRNode, int * minWNode, int * maxWNode) {
//	if (lim <= 2 || lim < heurg->maxcq - (heurg->maxcq >> 2))
//		return greedyColoring(R, W, lim, minRNode, maxRNode, minWNode, maxWNode);
//
//	int size = stackColoring(R, W, lim, minRNode, maxRNode, minWNode, maxWNode);
//
//	if (lim >= 3 && size == lim) {
//		int vidx;
//		NODETYPE * nodeS;
//		NODETYPE * nodeE;
//		NODETYPE * nodeEE;
//		int sentinel = heurg->n << 1;
//
//		if (E == NULL) {
//			int nnodes = NODEIDX(heurg->n-1) + 1;
//			E = (NODETYPE *) calloc((nnodes << 1) + nnodes, WSIZE);
//			EE = E + nnodes;
//			S = EE + nnodes;
//			memsz += (nnodes << (LOGW + 1)) + nnodes;
//		} else {
//			DELALL(EE + *minWNode, *maxWNode - *minWNode + 1);
//			DELALL(S + *minWNode, *maxWNode - *minWNode + 1);
//		}
//
//		int tsz = 0, nsz = size;
//		int k;
//
//		int i, curColor;
//		int minSNode;
//		int maxSNode;
//		int minENode, maxENode;
//
//		for (k = 1;
//				k == 1
//						|| (nsz + tsz / k < tsz / (k - 1)
//								|| -((double) nsz + tsz) / k
//										+ ((double) tsz) / (k - 1) > 0.8);
//				k++) {
//			minSNode = *minWNode;
//			maxSNode = *maxWNode;
//			tsz += nsz;
//			COPYALL(E+minSNode, EE+minSNode, maxSNode - minSNode + 1);
//			for (curColor = 0; curColor < nsz - 1; curColor++) {
//				for (i = nextInColor[heurg->n + curColor]; i < sentinel; i =
//						nextInColor[i])
//					S[NODEIDX(i)] = ADDTONODE(S[NODEIDX(i)], IDXINNODE(i));
//
//				addAll(E, S, minSNode, maxSNode + 1);
//				DELALL(EE + minSNode, maxSNode - minSNode + 1);
//				for (i = nextInColor[heurg->n + curColor + 1]; i < sentinel; i =
//						nextInColor[i])
//					removeAll(E, NEIG(heurg, i), minSNode, maxSNode + 1);
//
//				minENode = minNode(E, minSNode, maxSNode);
//				maxENode = maxNode(E, maxSNode, minENode);
//				nodeE = (E + minENode);
//				vidx = NODELEAST(*nodeE);
//				while (vidx >= 0) {
//					int v = NELEM(minENode) + vidx;
//					removeAll(E, NEIG(heurg, v), minENode, maxENode + 1);
//					*nodeE = DELFROMNODE(*nodeE, vidx);
//					nodeS = (S + minENode);
//					*nodeS = DELFROMNODE(*nodeS, vidx);
//					nodeEE = (EE + minENode);
//					*nodeEE = ADDTONODE(*nodeEE, vidx);
//					minENode = minNode(E, minENode, maxENode);
//					nodeE = (E + minENode);
//					vidx = NODELEAST(*nodeE);
//				}
//			}
//
//			for (i = nextInColor[heurg->n + curColor]; i < sentinel; i =
//					nextInColor[i])
//				S[NODEIDX(i)] = ADDTONODE(S[NODEIDX(i)], IDXINNODE(i));
//			minSNode = minNode(S, minSNode, maxSNode);
//			maxSNode = maxNode(S, maxSNode, minSNode);
//			nsz = stackColoring(S, E, lim, &minSNode, &maxSNode, &minENode,
//					&maxENode);
//		}
//		if (k > 2)
//			greedyColoring(R, W, size - (tsz / (k - 1)), minRNode, maxRNode,
//					minWNode, maxWNode);
//	}
//
//	return size;
//}
